//
// Created by Semir on 2020/4/22.
//

#include <iostream>
#include <vector>

using namespace std;

struct Bag {
    int total;
    int w[5], v[5];
};

const int MAX_M = 32005;
const int MAX_N = 65;
int m, n;
vector<Bag*> bags(60);
int dp[MAX_M];

int main() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        if (z == 0) {
            bags[i] = new Bag;
            bags[i]->total = 1;
            bags[i]->w[1] = x;
            bags[i]->v[1] = x * y;
        } else {
            if (bags[z]->total == 1) {
                bags[z]->total = 2;
                bags[z]->w[2] = bags[z]->w[1] + x;
                bags[z]->v[2] = bags[z]->v[1] + x * y;
            } else {
                bags[z]->total = 4;
                bags[z]->w[3] = bags[z]->w[1] + x;
                bags[z]->v[3] = bags[z]->v[1] + x * y;
                bags[z]->w[4] = bags[z]->w[2] + x;
                bags[z]->v[4] = bags[z]->v[2] + x * y;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (bags[i] == nullptr) {
            continue;
        }
        for (int j = m; j >= 0; j--) {
            for (int k = 1; k <= bags[i]->total; k++) {
                if (j >= bags[i]->w[k]) {
                    dp[j] = max(dp[j], dp[j - bags[i]->w[k]] + bags[i]->v[k]);
                }
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}